#leetcode题目36：有效的数独
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n^2)
#方法：回溯，哈希表
from typing import List
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        m=len(board)
        n=len(board[0])

        if not m or not n or m!=n:
            return False


        rows=[set() for _ in range(m)]
        cols=[set() for _ in range(n)]
        boxes=[[set() for _ in range(n//3)] for _ in range(m//3)]#9个3*3的盒子
        for i in range(m):
            for j in range(n):
                if board[i][j]!=".":
                    if board[i][j] in rows[i] or board[i][j] in cols[j] or board[i][j] in boxes[i//3][j//3]:
                        return False
                    rows[i].add(board[i][j])
                    cols[j].add(board[i][j])
                    boxes[i//3][j//3].add(board[i][j])
        return True

#测试数据
board=[
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]

#预期输出：True
solution=Solution()
print(solution.isValidSudoku(board))


board=[
    ["8","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
#预期输出：False
solution=Solution()
print(solution.isValidSudoku(board))